<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>PlanarGC: Tutorial: CutPlanar</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">PlanarGC
   &#160;<span id="projectnumber">1.0.2</span>
   </div>
  </td>
   <td>        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
</td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.1.2 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a00005.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Data Structures</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Pages</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Tutorial: <a class="el" href="a00014.html">CutPlanar</a> </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p><a class="el" href="a00014.html">CutPlanar</a> finds a minimal cut in an arbitrary planar graph, i.e., in a graph that can be embedded into the plane. Instead of an explicit embedding of vertices and edges, an algebraic embedding is used.<br/>
 This embedding is given by a counter-clockwise order of all edges that are adjacent to a given vertex:</p>
<div class="image">
<img src="introGraph.png" alt="introGraph.png"/>
<div class="caption">
Example of a Planar Graph</div></div>
<p>In order to compute the cut, the following steps have to be performed:</p>
<ol type="1">
<li>Define the <a class="el" href="a00005.html#sec_planar">planar embedding</a>.</li>
<li>Compute the <a class="el" href="a00005.html#sec_maxflow">maximum flow</a> with respect to a source and a sink.</li>
<li><a class="el" href="a00005.html#sec_getcut">Extract the minimal cut</a> as a vertex-based or an edge-based representation.</li>
</ol>
<p>In the following sections, we explain these steps with respect to the graph sketched in the image above.</p>
<h1><a class="anchor" id="sec_planar"></a>
Planar Embedding</h1>
<p>First, we have to define the algebraic embedding of the planar graph. To do this, we construct an array of 9 vertices, an array of 13 edges and an array of 6 faces (Face A, ..., Face F):</p>
<div class="fragment"><div class="line"><a class="code" href="a00027.html">PlanarVertex</a> vertex[ 9];</div>
<div class="line"><a class="code" href="a00025.html">PlanarEdge</a>     edge[13];  </div>
<div class="line"><a class="code" href="a00026.html">PlanarFace</a>     face[ 6];</div>
</div><!-- fragment --><p>Next, we define the edges by providing a start and a target vertex as well as a left and a right face. In this example, we assume an undirected edge with unit capacity, i.e., the capacity in both directions is 1.</p>
<div class="fragment"><div class="line">edge[ 0].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+0, vertex+1, face+5, face+0, 1, 1);  </div>
<div class="line">edge[ 1].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+0, vertex+2, face+0, face+1, 1, 1);  </div>
<div class="line">edge[ 2].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+0, vertex+3, face+1, face+5, 1, 1);  </div>
<div class="line">edge[ 3].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+1, vertex+2, face+2, face+0, 1, 1);  </div>
<div class="line">edge[ 4].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+2, vertex+3, face+3, face+1, 1, 1);  </div>
<div class="line">edge[ 5].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+1, vertex+6, face+5, face+2, 1, 1);  </div>
<div class="line">edge[ 6].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+2, vertex+4, face+2, face+3, 1, 1);  </div>
<div class="line">edge[ 7].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+3, vertex+5, face+3, face+5, 1, 1);  </div>
<div class="line">edge[ 8].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+4, vertex+5, face+4, face+3, 1, 1);  </div>
<div class="line">edge[ 9].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+4, vertex+7, face+2, face+4, 1, 1);  </div>
<div class="line">edge[10].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+5, vertex+8, face+4, face+5, 1, 1);  </div>
<div class="line">edge[11].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+6, vertex+7, face+5, face+2, 1, 1);  </div>
<div class="line">edge[12].<a class="code" href="a00025.html#a5925dae5531f32dce166b70d510b68ad">setEdge</a>(vertex+7, vertex+8, face+5, face+4, 1, 1);</div>
</div><!-- fragment --><p>Finally, to every vertex a list of adjacent edges has to be provided. The edges in every list are ordered in a counter-clockwise sense.</p>
<div class="fragment"><div class="line"><a class="code" href="a00025.html">PlanarEdge</a> *edges_CCW[4]; <span class="comment">// every vertex has at most four adjacent edges</span></div>
<div class="line"></div>
<div class="line">edges_CCW[0] = edge+ 0; edges_CCW[1] = edge+ 2; edges_CCW[2] = edge+ 1;</div>
<div class="line">vertex[0].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 3);  </div>
<div class="line">edges_CCW[0] = edge+ 0; edges_CCW[1] = edge+ 3; edges_CCW[2] = edge+ 5;</div>
<div class="line">vertex[1].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 3);  </div>
<div class="line">edges_CCW[0] = edge+ 1; edges_CCW[1] = edge+ 4; edges_CCW[2] = edge+ 6; edges_CCW[3] = edge+ 3;</div>
<div class="line">vertex[2].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 4);  </div>
<div class="line">edges_CCW[0] = edge+ 2; edges_CCW[1] = edge+ 7; edges_CCW[2] = edge+ 4;</div>
<div class="line">vertex[3].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 3);  </div>
<div class="line">edges_CCW[0] = edge+ 6; edges_CCW[1] = edge+ 8; edges_CCW[2] = edge+ 9;</div>
<div class="line">vertex[4].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 3);  </div>
<div class="line">edges_CCW[0] = edge+ 7; edges_CCW[1] = edge+10; edges_CCW[2] = edge+ 8;</div>
<div class="line">vertex[5].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 3);  </div>
<div class="line">edges_CCW[0] = edge+ 5; edges_CCW[1] = edge+11;</div>
<div class="line">vertex[6].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 2);  </div>
<div class="line">edges_CCW[0] = edge+ 9; edges_CCW[1] = edge+12; edges_CCW[2] = edge+11;</div>
<div class="line">vertex[7].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 3);  </div>
<div class="line">edges_CCW[0] = edge+10; edges_CCW[1] = edge+12;</div>
<div class="line">vertex[8].<a class="code" href="a00027.html#a96f79bc032b6354c1c436eee2e72256b">setEdgesCCW</a>(edges_CCW, 2);  </div>
</div><!-- fragment --><h1><a class="anchor" id="sec_maxflow"></a>
Maximum Flow</h1>
<p>Now, we have to compute the maximum flow. In order to do this via <a class="el" href="a00014.html">CutPlanar</a>, we have to initialize <a class="el" href="a00014.html">CutPlanar</a> with the planar graph as well as a source and a sink.</p>
<div class="fragment"><div class="line"><a class="code" href="a00014.html">CutPlanar</a> planar_cut;</div>
<div class="line"></div>
<div class="line">planar_cut.<a class="code" href="a00014.html#a415e8e9f3222cc883aa92964847d9fbe">initialize</a>(9,vertex, 13,edge, 6,face);</div>
<div class="line">planar_cut.<a class="code" href="a00014.html#a8ea383a874b9b9eb68708b0dc41df26d">setSource</a>(2);</div>
<div class="line">planar_cut.<a class="code" href="a00014.html#a4b7c9212072ac58174b4ad0a9691b961">setSink</a>  (6);</div>
</div><!-- fragment --><p>Finally, we have to compute the value of the maximum flow. This is the most time consuming method of the class and is called via</p>
<div class="fragment"><div class="line"><span class="keywordtype">double</span> flow;</div>
<div class="line"></div>
<div class="line">flow = planar_cut.<a class="code" href="a00014.html#a843ed38fe06946e7fdbdad011a71639e">getMaxFlow</a>();</div>
</div><!-- fragment --><h1><a class="anchor" id="sec_getcut"></a>
Extract Minimal Cut</h1>
<p>For most applications, we are not only interested in the value of the minimum cut, but also in the cut itself. The classical way in describing this cut is to assign a binary labeling to each vertex of the graph. This labeling can be provided via <a class="el" href="a00014.html#acf0d49ee5b2e7ce0fa5fda70898bbd23">CutPlanar::getLabel</a> or <a class="el" href="a00014.html#aa170890c9d7ed4a668cfa738ad7ed503">CutPlanar::getLabels</a></p>
<div class="fragment"><div class="line"><a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989">CutPlanar::ELabel</a> label;</div>
<div class="line">vector&lt;int&gt;       labels;</div>
<div class="line"></div>
<div class="line">label  = planar_cut.<a class="code" href="a00014.html#acf0d49ee5b2e7ce0fa5fda70898bbd23">getLabel</a>(5);                              <span class="comment">// returns &#39;CutPlanar::LABEL_SOURCE&#39;</span></div>
<div class="line">label  = planar_cut.<a class="code" href="a00014.html#acf0d49ee5b2e7ce0fa5fda70898bbd23">getLabel</a>(6);                              <span class="comment">// returns &#39;CutPlanar::LABEL_SINK&#39;</span></div>
<div class="line">labels = planar_cut.<a class="code" href="a00014.html#aa170890c9d7ed4a668cfa738ad7ed503">getLabels</a>(<a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989a4a87e4f2960247d1c734c50865a6c842">CutPlanar::LABEL_SOURCE</a>);       <span class="comment">// returns {0,1,2,3,4,5,7,8} </span></div>
<div class="line">labels = planar_cut.<a class="code" href="a00014.html#aa170890c9d7ed4a668cfa738ad7ed503">getLabels</a>(<a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989a322bd84e5ca9be01787d0c08b488c127">CutPlanar::LABEL_SINK</a>);         <span class="comment">// returns {6} </span></div>
</div><!-- fragment --><p>It is known that the edges of a planar cut define a closed path in the dual graph. To extract either this path or the vertices at the boundary of this path, the methods <a class="el" href="a00014.html#afde8ab5c6700ea7ab214e2bb8082086f">CutPlanar::getCircularPath</a> and <a class="el" href="a00014.html#a2ecd800c5a00d2839f282ba69d360d62">CutPlanar::getCutBoundary</a> are provided</p>
<div class="fragment"><div class="line">vector&lt;int&gt; dual_path;</div>
<div class="line">vector&lt;int&gt; boundary;</div>
<div class="line"></div>
<div class="line">dual_path = planar_cut.<a class="code" href="a00014.html#afde8ab5c6700ea7ab214e2bb8082086f">getCircularPath</a>();                             <span class="comment">// returns face IDs {5,2}</span></div>
<div class="line">boundary  = planar_cut.<a class="code" href="a00014.html#a2ecd800c5a00d2839f282ba69d360d62">getCutBoundary</a>(<a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989a4a87e4f2960247d1c734c50865a6c842">CutPlanar::LABEL_SOURCE</a>);       <span class="comment">// returns vertex IDs {7,1}</span></div>
<div class="line">boundary  = planar_cut.<a class="code" href="a00014.html#a2ecd800c5a00d2839f282ba69d360d62">getCutBoundary</a>(<a class="code" href="a00014.html#a0e28d67a0303b0b1a43bb9abbad02989a322bd84e5ca9be01787d0c08b488c127">CutPlanar::LABEL_SINK</a>);         <span class="comment">// returns vertex IDs {6,6}</span></div>
</div><!-- fragment --><p>The complete code can be seen here: <a class="el" href="a00001.html">cutplanar.cpp</a>. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<hr class="footer"/><address style="text-align: right;"><small>
  &copy; 2009 - 2013 by Eno T&ouml;ppe, Frank R. Schmidt
  <br/>
  generated by <a href="http://www.doxygen.org/index.html" target="_blank">Doxygen</a>
</small></address>
